package com.chenken.graph;

import java.util.Set;

/**
 * 
 * @author ken.chen
 *
 * @param <V>	顶点
 * @param <E>	边
 */
public abstract class Graph<V,E> {
	
	protected WeightManager<E> weightManager;
	
	public Graph() {}
	
	public Graph(WeightManager<E> weightManager){
		this.weightManager = weightManager;
	}
	
	/**
	 * 边的数量
	 * @return
	 */
	public abstract int edgesSize();
	
	/**
	 * 顶点的数量
	 * @return
	 */
	public abstract int verticesSize();

	/**
	 * 添加一个顶点
	 */
	public abstract void addVertex(V v);
	
	/**
	 * 添加一条边
	 * @param from	
	 * @param to
	 */
	public abstract void addEdge(V from,V to);
	
	/**
	 * 添加一条边
	 * @param from	
	 * @param to
	 * @param weight	权值
	 */
	public abstract void addEdge(V from,V to,E weight);
	
	/**
	 * 删除一个顶点
	 * @param v
	 */
	public abstract void removeVertex(V v);
	
	/**
	 * 删除一条边
	 * @param from	
	 * @param to
	 */
	public abstract void removeEdge(V from,V to);
	
	/**
	 * 广度优先搜索	Breadth First Search
	 * @param begin
	 */
	public abstract void bfs(V begin,VertexVisitor<V> visitor);
	
	/**
	 * 深度优先搜索	Depth First Search
	 * @param begin
	 */
	public abstract void dfs(V begin,VertexVisitor<V> visitor);
	
	/**
	 * 最小生成树
	 * @return	边的集合
	 */
	public abstract Set<EdgeInfo<V, E>> mst();
	
	/**
	 * 访问器
	 */
	public interface VertexVisitor<V>{
		boolean visit(V v);
	}
	
	/**
	 * 权重管理
	 */
	public interface WeightManager<E>{
		
		/**
		 * 两个权重比较
		 * @param w1
		 * @param w2
		 * @return
		 */
		int compare(E w1,E w2);
		
		/**
		 * 两个权重相加
		 * @param w1
		 * @param w2
		 * @return
		 */
		E add(E w1,E w2);
		
	}
	
	/**
	 * 边信息
	 */
	public static class EdgeInfo<V,E>{
		V from;
		V to;
		E weight;
		public EdgeInfo(V from, V to, E weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
		@Override
		public String toString() {
			return "EdgeInfo [from=" + from + ", to=" + to + ", weight=" + weight + "]";
		}
	}
}
